The present invention relates to the communication of digital data and more particularly to a pseudorandom convolutional interleaving technique and the synchronization of a convolutional deinterleaver.
Digital data can be communicated using various well known techniques. In some communication schemes, the data is encoded before transmission to provide "symbols" that are transmitted to a receiver, which decodes the symbols to recover the desired data.
In certain instances, the data channel over which data is communicated exhibits mutually dependent signal transmission impairments. An example of such a channel is one that fades in and out over time. Another type of impairment known as "multipath" occurs when signals arrive at a receiver over two or more paths of different lengths. The result is that that signals arrive out of phase with each other, distorting the cumulative received signal.
Switching noise and other burst noise can also appear on communication channels and degrade the performance of the communications equipment. All such time-correlated channel impairments result in a statistical dependence among successive data symbol transmissions. Thus, the disturbances tend to cause errors that occur in bursts, instead of isolated errors during a transmission. One technique for reducing such errors is the use of time diversity or "interleaving."
Interleaving digital data (e.g., codeword symbols representing coded information) before transmission and deinterleaving the data after reception causes bursts of channel errors to be spread out in time. This enables the receiver to treat the errors as if they were random errors. Thus, the idea behind the technique of interleaving is to separate successive symbols in time. The intervening times are filled by other symbols. Separating the symbols in time enables known random error correcting codes to be useful in correcting burst noise errors.
Various techniques are known for decoding transmitted symbols. One such technique is the well known Viterbi decoding algorithm, which uses the trellis structure of a convolutional code and systematically exploits the periodic remerging of the trellis paths to determine the survivors. For any convolutional code, the output of a Viterbi decoder is a sequence of estimated information digits which is maximum likelihood conditioned upon the received sequence. The Viterbi decoding algorithm is particularly suitable for decoding symbols transmitted over satellite channels. The Viterbi algorithm is explained in detail in G. D. Forney, Jr., "The Viterbi Algorithm," Proceedings of the IEEE, Vol. 61, No. 3, March 1973.
Conventional interleavers and deinterleavers are addressed sequentially. This means that the codeword symbols are input to the interleaver input ports and output from the interleaver output ports in an orderly, sequential fashion. Likewise, the interleaved symbols received via the communications channel are input to the deinterleaver input ports and output from the deinterleaver output ports in the same orderly sequential manner. A problem with this arrangement is that even when a sequentially addressed deinterleaver is not synchronized with the corresponding interleaver, it can still output runs of correctly deinterleaved symbols. If these runs are long enough, a Viterbi decoder following the deinterleaver may indicate false synchronization. In addition, an interleaver that is addressed sequentially can be defeated by interference that is pulsed at the same period as the interleaver address cycle. Such a situation will compromise the accuracy of the communication system.
It would be advantageous to provide an interleaving system that avoids the problems of false synchronization noted above. It would be further advantageous to provide a randomly addressed interleaver/deinterleaver structure, with a simple yet effective means for synchronizing the addressing of the deinterleaver to the addressing used at the interleaver. The present invention provides a synchronization scheme for use in a pseudorandom interleaver/deinterleaver structure which enjoys these advantages.